package tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目：二叉树的最大深度
 * @Author Gavin
 * @date 2021.12.23 21:47
 */
public class tree_4 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);

        TreeNode c_1=new TreeNode(2);
        TreeNode c_2=new TreeNode(4);
        TreeNode c_3=new TreeNode(5);
        TreeNode c_4=new TreeNode(6);
        root.left=c_1;
        root.right=c_2;
        c_1.left=c_3;
        c_3.right=c_4;

        System.out.println(solution_1(root));

    }
    //1.递归的方法，求最大深度
    public static int solution_1(TreeNode root){
        //首先确定递归的终止条件
        if(root==null)return 0;
        return Math.max(solution_1(root.left),solution_1(root.right))+1;
    }

    //2.按层进行遍历，使用一个额外的队列来处理，比较常用
    public static int solution_2(TreeNode root){
        int depth=0;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode pre=queue.poll();
                if(pre.left!=null){
                    queue.add(pre.left);
                }
                if(pre.right!=null){
                    queue.add(pre.right);
                }
                depth++;
            }
        }
        return depth;
    }
}
